— algorithm, golang — 1 min read
最近学Go,感觉挺不错的。闲来无事用它写了几种常用的基础算法。
思想很简单,实现起来为了方便每次以left作为基准,也可以使用BFS来节省递归栈:
最短路核心思想就是Relax操作。效率高的单源最短路有下面两种算法:
O(kE)
其中k<<V
;最好的情况即一次BFS,时间复杂度为 O(E)
,然而对于某些精心构造的图,复杂度可以达到Bellman-ford级别:O(VE)
。
下面构图使用的是邻接表(适用于稀疏图),也可以用邻接矩阵(适用于稠密图)。字符串匹配经典算法。关键在于维护一个这样的关系:x[i-next[i]...i-1]=x[0...next[i]-1]
To Be Continue...